/*kZime*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define MAXN

using namespace std;

int f[2333][2333], n, m; 

inline int read() {
	int k = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar())if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}

void floyd() {
	for(int k = 1; k <= n; k++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++){
				f[i][j] = min(f[i][k] + f[k][j], f[i][j]);
			}
		}
	}
	
	while(true) {
		int x = read();
		int y = read();
		printf("%d\n", f[x][y]);
	}
	
}


int main() {
#ifndef LOCAL
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#else
//	freopen("in.txt", "r", stdin);
#endif
	memset(f, 127 / 2, sizeof(f));
	n = read();
	m = read();
	for(int i = 1; i <= m; i++) {
		int x = read();
		int y = read();
		f[x][y] = 1;
		f[y][x] = 1;
	}
	
	floyd();
	
	return 0;
}
/*
6 10
1 2
1 3
3 4
2 4
2 5
4 5
5 6
1 6
3 2
2 6

*/
